package com.huangyi;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Solution2 solution2 = new Solution2();

        // 测试单词拆分
        System.out.println("=== 单词拆分 ===");
        String s1 = "leetcode";
        List<String> dict1 = Arrays.asList("leet", "code");
        System.out.println("测试用例1: s = \"leetcode\", wordDict = [\"leet\", \"code\"]");
        System.out.println("能否拆分: " + solution.wordBreak(s1, dict1)); // 预期输出: true

        String s2 = "applepenapple";
        List<String> dict2 = Arrays.asList("apple", "pen");
        System.out.println("\n测试用例2: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]");
        System.out.println("能否拆分: " + solution.wordBreak(s2, dict2)); // 预期输出: true

        String s3 = "catsandog";
        List<String> dict3 = Arrays.asList("cats", "dog", "sand", "and", "cat");
        System.out.println("\n测试用例3: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]");
        System.out.println("能否拆分: " + solution.wordBreak(s3, dict3)); // 预期输出: false

        // 测试环绕字符串中唯一的子字符串
        System.out.println("\n=== 环绕字符串中唯一的子字符串 ===");
        String p1 = "a";
        System.out.println("测试用例1: s = \"a\"");
        System.out.println("子字符串个数: " + solution2.findSubstringInWraproundString(p1)); // 预期输出: 1

        String p2 = "cac";
        System.out.println("\n测试用例2: s = \"cac\"");
        System.out.println("子字符串个数: " + solution2.findSubstringInWraproundString(p2)); // 预期输出: 2

        String p3 = "zab";
        System.out.println("\n测试用例3: s = \"zab\"");
        System.out.println("子字符串个数: " + solution2.findSubstringInWraproundString(p3)); // 预期输出: 6
    }

    // 单词拆分
    static class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            // 优化：HashSet 查找 O(1)
            Set<String> hash = new HashSet<>(wordDict);

            // 先保存原长度（关键）
            int n = s.length();

            // dp[i]: 前 i 个字符能否拆分
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;  // 空串可以拆分

            // 加空格对齐下标
            s = " " + s;

            for (int i = 1; i <= n; i++) {
                for (int j = i; j >= 1; j--) {
                    // 前半部分能拆分 && 后半部分在字典
                    if (dp[j - 1] && hash.contains(s.substring(j, i + 1))) {
                        dp[i] = true;
                        break;  // 找到即停止
                    }
                }
            }

            return dp[n];
        }
    }

    // 环绕字符串中唯一的子字符串
    static class Solution2 {
        public int findSubstringInWraproundString(String s) {
            int n = s.length();
            char[] ch = s.toCharArray();

            // dp[i]: 以位置 i 结尾的最长连续长度
            int[] dp = new int[n];
            Arrays.fill(dp, 1);

            // hash[c]: 以字符 c 结尾的最长连续长度
            int[] hash = new int[26];

            // 计算每个位置的连续长度
            for (int i = 1; i < n; i++) {
                if (ch[i - 1] + 1 == ch[i] || (ch[i - 1] == 'z' && ch[i] == 'a')) {
                    dp[i] = dp[i - 1] + 1;
                }
            }

            // 记录每个字符的最大连续长度
            for (int i = 0; i < n; i++) {
                hash[ch[i] - 'a'] = Math.max(hash[ch[i] - 'a'], dp[i]);
            }

            // 累加所有字符的贡献
            int ret = 0;
            for (int i = 0; i < 26; i++) {
                ret += hash[i];
            }

            return ret;
        }
    }
}